#include <cassert>
#include <cstdio>

typedef unsigned long long ull;

const int N = 1e6 + 5, bit = 64;
int n, m, c, k, cont;
bool vis[bit], used[bit];

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("zoo.in", "r", stdin);
  freopen("zoo.out", "w", stdout);
#endif
#endif

  scanf("%d%d%d%d", &n, &m, &c, &k);
  ull a;
  for (int i = 1; i <= n; ++i) {
    scanf("%llu", &a);
    for (int j = 0; j < bit; ++j) {
      if ((a >> j) & 1) used[j] = true;
    }
  }
  for (int i = 1, p, q; i <= m; ++i) {
    scanf("%d%d", &p, &q);
    if (!vis[p]) { vis[p] = true; }
  }
  for (int i = 0; i < bit; ++i) {
    if (vis[i] && (!used[i])) ++cont;
  }
  if (k - cont == 64 && n == 0) puts("18446744073709551616");
  else
    printf("%llu", (k - cont == 64) ? (1ull << 63) - n + (1ull << 63)
                                    : ((1ull << (k - cont)) - n));
  return 0;
}